package cxydmmszl.chapter09.t168;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 在有序旋转数组中找到最小值
 * <li style="color: green;">Desc</li>
 * 有序数组 arr 可能经过一次旋转处理，也可能没有，且 arr 可能存在重复的数。
 * 例如，有序数组[1, 2, 3, 4, 5, 6, 7]，可以旋转处理成[4, 5, 6,  7, 1, 2, 3]等。
 * 给定一个可能旋转过的有序数组 arr，返回 arr 中的最小值。
 * <br/><br/>[要求]<br/>
 * 期望复杂度为 O(logn)
 * <br/><br/>备注<br/>
 * 1⩽N⩽10^6<br/>
 * 1⩽arr[i]⩽10^9
 * <li style="color: green;">Input</li>
 * 第一行一个整数N表示数组大小。
 * 接下来N个数表示数组内的数。
 * <li style="color: green;">Output</li>
 * 输出一个整数表示答案
 * <li style="color: blue;">Link</li> CD74
 *
 * @author habitplus
 * @since 2021-10-10 15:41
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        int num = findMinInRotateArr(arr);

        System.out.println(num);
    }

    private static int findMinInRotateArr(int[] arr) {
        if (arr == null || arr.length == 0 ) return 0;

        int l = 0;
        int r = arr.length - 1;
        int mid;
        while (l < r) {
            if (l == r - 1) {
                break;
            }
            if (arr[l] < arr[r]) {
                // arr[l,r] 没有旋转，直接返回 arr[l]
                return arr[l];
            }
            // 下面是 arr[l, r] 有经过旋转的情况
            mid = (l + r) / 2;
            if (arr[l] > arr[mid]) {
                // 断点在 arr[l, mid] 上
                r = mid;
            } else if (arr[mid] > arr[r]){
                // 断点在 arr[mid, r] 上
                l = mid;
            } else {
                // arr[l] >= arr[r]
                // arr[l] <= arr[mid]
                // arr[mid] <= arr[r]
                // 说明 arr[l] == arr[mid] == arr[r]
                while (l < mid) {
                    if (arr[l] == arr[mid]) {
                        l++;
                    } else if (arr[l] < arr[mid]) {
                        return arr[l];
                    } else {
                        r = mid;
                        break;
                    }
                }
            }
        }

        return Math.min(arr[l], arr[r]);
    }
}
